距离上次更新已经 1713 天了,文章内容可能已经过时。

课程主页: https://www.davidsilver.uk/teaching/

这里回顾David silver 强化学习 Lecture 4的课程内容,这一讲简单介绍了不基于模型的预测。

介绍

上一讲介绍了如何通过DP进行规划,那里假设MDP已知;这一讲介绍不基于模型的预测,即对未知的MDP预测其价值函数。

蒙特卡洛学习

  • 目标:通过策略π下的信息学习vπ

    S1,A1,R2,,Skπ
  • 注意回报(return)是折扣奖励:

    Gt=Rt+1+γRt+2++γT1RT
  • 回报价值函数是回报(return)的期望:

    vπ(s)=Eπ[Gt|St=s]
  • 蒙特卡洛策略评估使用经验均值回报而非期望回报

具体方式如下:

  • 为了评估状态s
  • 在一幕(episode)中访问状态s的第一个(每一个)时间戳t
  • 增加计数器N(s)N(s)+1
  • 增加总回报S(s)S(s)+Gt
  • 价值通过回报的均值估计V(s)=S(s)/N(s)
  • 根据大数定律,随着N(s)V(s)vπ(s)
增量均值

序列x1,x2,的均值μ1,μ2,可以通过增量方式计算:

μk=1kj=1kxj=1k(xk+j=1k1xj)=1k(xk+(k1)μk1)=μk1+1k(xkμk1)
增量MC更新
  • 根据上述公式,可以通过增量方式更新V(s)

  • 对于回报为Gt的状态St

    N(St)N(St)+1V(St)V(St)+1N(St)(GtV(St))
  • 在非平稳问题中,跟踪连续平均值(即忘掉旧幕(episodes))可能很有用。

    V(St)V(St)+α(GtV(St))

时序差分学习(Temporal-Difference Learning)

  • TD方法可直接从经验中学习
  • TD是不基于模型的:不需要了解MDP转移/奖励
  • TD通过bootstrapping从不完整的幕中学习
  • TD根据猜测更新猜测
MC and TD
  • 目标:在策略π下根据经验在线学习vπ

  • 增量MC

    • 根据实际回报Gt更新价值V(St)V(St)V(St)+α(GtV(St))
  • 考虑最简单的时序差分算法:TD(0)

    • 通过估计回报Rt+1+γV(St+1)更新V(St)

      V(St)V(St)+α(Rt+1+γV(St+1)V(St))
    • Rt+1+γV(St+1)被称为TD目标

    • δt=Rt+1+γV(St+1)V(St)被称为TD误差

MC vs TD的优劣势对比(1)
  • TD在知道最终结果之前就可以学习
    • TD可以在每一步后在线学习
    • MC必须等到每一幕结束后知道回报的时刻
  • TD可以在不知道最终结果的条件下学习
    • TD可以从不完全序列中学习
    • MC只能从完全序列中学习
    • TD可以在连续(非终止)环境中运行
    • MC只能在幕(终止)环境中运行
偏差/方差权衡
  • 回报Gt=Rt+1+γRt+2++γT1RTvπ(St)的无偏估计
  • 真正的TD目标Rt+1+γvπ(St+1)vπ(St)的无偏估计
  • TD目标Rt+1+γV(St+1)vπ(St)的有偏估计
  • TD目标比回报的方差要小的多:
    • 因为回报依赖于很多随机动作,转移以及奖励
    • TD目标只依赖一个随机动作,转移以及奖励
MC vs TD的优劣势对比(2)
  • MC有高方差,无偏
    • 很好的收敛性
    • 对初始值不敏感
    • 很好理解和使用
  • TD有低方差,有偏
    • 通常比MC更高效
    • TD(0)收敛于vπ(s)
    • 对初始值更敏感
批量MC和TD
  • MC和TD都收敛:V(s)vπ(s)随着经验

  • 但是对于有限经验的批处理解决方案呢?

    s11,a11,r21,,sT11s1K,a1K,r2K,,sTKK
    • 例如:重复对第k[1,K]幕采样
    • 对第k幕应用MC或TD(0)
MC vs TD的优劣势对比(3)

由TD的表达式,不难得到

  • TD利用了马尔可夫性
    • 通常在马尔可夫环境下更高效
  • MC没有利用马尔可夫性
    • 通常在非马尔可夫环境下更高效
对比
MC
V(St)V(St)+α(GtV(St))

TD
V(St)V(St)+α(Rt+1+γV(St+1)V(St))

DP
V(St)Eπ[Rt+1+γV(St+1)]

Bootstrapping和采样
  • Bootstrapping:更新涉及估计
    • MC不使用Bootstrap
    • DP使用Bootstrap
    • TD使用Bootstrap
  • 采样:
    • MC使用采样
    • DP不使用采样
    • TD使用采样

TD(λ)

假设TD查看未来的n

n步回报
  • 考虑如下n步回报:

    n=1(TD)Gt(1)=Rt+1+γV(St+1)n=2Gt(2)=Rt+1+γRt+2+γ2V(St+2)n=(MC)Gt()=Rt+1+γRt+2++γT1RT
  • 定义n步回报

    Gt(n)=Rt+1+γRt+2++γn1Rt+n+γnV(St+n)
  • n步时序差分学习

    V(St)V(St)+α(Gt(n)V(St))
λ回报

接下来考虑对不同步数的回报做加权:

  • λ回报Gtλ结合了所有n步回报Gt(n)

  • 使用权重(1λ)λn1

    Gtλ=(1λ)n=1λn1Gt(n)
  • TD(λ)的前向视角(Forward-view)

    V(St)V(St)+α(GtλV(St))
TD(λ)的前向视角

  • 通过λ回报更新价值函数
  • 通过对未来的前瞻性计算Gtλ
  • 像MC一样,只能根据完整的幕(episodes)计算
TD(λ)的反向视角
  • 前向视角提供理论
  • 反向提供了机制
  • 从不完整的序列在线更新每一步

为了讨论反向视角,首先定义合格轨迹:

E0(s)=0Et(s)=γλEt1(s)+1(St=s)
  • 保持每个状态s的合格轨迹Et(s)

  • 对每个状态s更新V(s)

  • 更新项正比于TD-误差δt和合格轨迹Et(s)

    δt=Rt+1+γV(St+1)V(St)V(s)V(s)+αδtEt(s)

TD(λ)TD(0)
  • λ=0,只有当前状态被更新

    Et(s)=1(St=s)V(s)V(s)+αδtEt(s)
  • 这等价于TD(0)更新

    V(St)V(St)+αδt
TD(1)和MC
  • 考虑在时间戳k一次访问s的一幕

  • 考虑TD(1)的合格轨迹

    Et(s)=γEt1(s)+1(St=s)={0 if t<kγtk if tk
  • TD(1)更新在线累积误差

    t=1T1αδtEt(s)=αt=kT1γtkδt
  • 在幕结束时,累计误差为

    δk+γδk+1+γ2δk+2++γT1kδT1
  • 利用公式δt=Rt+1+γV(St+1)V(St)对其处理可得

    δt+γδt+1+γ2δt+2++γT1tδT1=Rt+1+γV(St+1)V(St)+γRt+2+γ2V(St+2)γV(St+1)+γ2Rt+3+γ3V(St+3)γ2V(St+2)+γT1tRT+γTtV(ST)γT1tV(ST1)=Rt+1+γRt+2+γ2Rt+3+γT1tRTV(St)=GtV(St)
  • 所以

    t=1T1αδtEt(s)=αt=kT1γtkδt=α(GkV(Sk))

更一般的,我们有如下定理:

定理

对于TD(λ)的前向视角和后向视角,所有更新的总和是相同的:

t=1TαδtEt(s)=t=1Tα(GtλV(St))1(St=s)

总之,TD(1)几乎等价于MC

离线更新

离线更新

  • 更新在一幕中累积
  • 但在幕结束时批量应用
在线更新
  • TD(λ)在每一幕的每一步中都进行更新
  • TD(λ)的前向反向视角有所不同
总结